package problem33;

//33. 搜索旋转排序数组
//https://leetcode.cn/problems/search-in-rotated-sorted-array/?envType=study-plan-v2&envId=top-interview-150

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length-1;
        while(l < r) {
            int m = l + (r - l)/2;
            // [l, m] [m+1, r] 必有一个区间有序, 一个区间无序
            // System.out.println(l + " " + r + " " + m);
            if(nums[l] < nums[m]) {
                //[l, m] 区间有序
                if(nums[l] <= target && nums[m] >= target) {
                    r = m;
                }else {
                    l = m+1;
                }
            }else {
                //[m+1, r] 区间有序
                if(nums[m+1] <= target && nums[r] >= target) {
                    l = m+1;
                }else {
                    r = m;
                }
            }
        }
        // System.out.println(l + " " + r);
        if(nums[l] == target) return l;
        return -1;
    }
}